package tree

import "gitee.com/ChanYeung/go-utils/collections"

//二叉树的中序遍历
func inorderTraversal(root *TreeNode) []int {
	var list []int
	var internal func(node *TreeNode)
	internal = func(node *TreeNode) {
		if node == nil {
			return
		}
		internal(node.Left)
		list = append(list, node.Val)
		internal(node.Right)
	}
	internal(root)
	return list
}

/**

	3
  1  2
4
*/
//后续遍历 非递归
func endTraversal(root *TreeNode) []int {
	result := []int{}
	s := collections.Stack{}
	p := root
	var lastR *TreeNode
	for p != nil || !s.IsEmpty() {
		if p != nil {
			//根节点，遍历左孩子
			s.Push(p)
			p = p.Left
		} else {
			//处理右子节点
			u := s.Peak().(*TreeNode)
			if u.Right != nil && u.Right != lastR { //u 右子节点不能重复遍历
				p = u.Right
			} else {
				s.Pop()
				result = append(result, u.Val)
				lastR = u
				p = nil //让栈弹出 回到父节点
			}

		}
	}
	return result
}

/**
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	//使用dfs  中序遍历  从root节点出发找到异侧节点==指定的p q 则该root时最近公共祖先
	if root == nil {
		return nil // 如果树为空，直接返回nil
	}
	if root == p || root == q {
		// 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
		return root
	}
	left := lowestCommonAncestor(root.Left, p, q)   // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
	right := lowestCommonAncestor(root.Right, p, q) // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
	if left == nil {
		return right // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
	}
	if right == nil {
		return left // 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
	}
	return root //从 root出发 找到p和q节点，root时候最近祖先
}
